package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         329,
		Discription: "矩阵中最长递增路径（不成环）",
		Level:       2,
		Labels: map[string]int{
			"矩阵":    1,
			"记忆化搜索": 1,
			"动态规划": 1,
			"递归":    1,
		},
	})
}

//从（0，0）开始进dfs，如果碰到算过的节点，则直接返回，没算过就再递归一层进行算
func LongestIncreasingPath(matrix [][]int) int {
	m := len(matrix)
	n := len(matrix[0])
	//maxLen[i][j]表示以（i，j)为起点的最长递增路径的长度（最小只有自己一个节点，也就是1）
	maxLens := make([][]int, m)
	for i := range maxLens {
		maxLens[i] = make([]int, n)
	}

	directions := [][]int{{0, 1}, {1, 0}, {-1, 0}, {0, -1}}
	var dfs func(int, int) int
	dfs = func(i, j int) int {
		res := 1
		for _, dir := range directions {
			x := i + dir[0]
			y := j + dir[1]
			if x < 0 || y < 0 || x >= m || y >= n {
				continue
			}
			if matrix[i][j] >= matrix[x][y] {
				continue
			}

			if maxLens[x][y] == 0 {
				maxLens[x][y] = dfs(x, y)
			}
			res = max(res, maxLens[x][y]+1)
		}

		return res
	}

	maxLen := 1
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if maxLens[i][j] == 0 {
				maxLens[i][j] = dfs(i, j)
			}
			maxLen = max(maxLen, maxLens[i][j])
		}
	}

	return maxLen
}
